package com.example.zz.example.datastructures;

import java.util.Arrays;

/**
 *  树：是一种数据结构。特点：每个结点有零个或多个子结点；没有父结点的结点称为根结点；每一个非根结点有且只有一个父结点；
 *  除了根结点外，每个子结点可以分为多个不相交的子树；树结构是一种非线性存储结构，存储的是具有“一对多”关系的数据元素的集合。
 *
 *
 */

public class TreeDemo {

    public static void main(String[] args) {

        int pre[] = {1, 2, 4, 7, 3, 5, 6, 8};
        int in[] = {4, 7, 2, 1, 5, 3, 8, 6};

        TreeNode treeNode = reConstructBinaryTree(pre, in);

    }

    public static TreeNode reConstructBinaryTree(int[] pre, int[] in) {
        if (pre.length == 0 || in.length == 0) {
            return null;
        }
        TreeNode root = new TreeNode(pre[0]);
        // 在中序中找到前序的根
        for (int i = 0; i < in.length; i++) {
            if (in[i] == pre[0]) {
                int[] newPreLeft = Arrays.copyOfRange(pre, 1, i + 1);
                int[] newInLeft = Arrays.copyOfRange(in, 0, i);
                root.left = reConstructBinaryTree(newPreLeft, newInLeft);
                // 左子树，注意 copyOfRange 函数，左闭右开
//                root.left = reConstructBinaryTree(Arrays.copyOfRange(pre, 1, i + 1), Arrays.copyOfRange(in, 0, i));
                // 右子树，注意 copyOfRange 函数，左闭右开
                root.right = reConstructBinaryTree(Arrays.copyOfRange(pre, i + 1, pre.length), Arrays.copyOfRange(in, i + 1, in.length));
                break;
            }
        }
        return root;


    }

    public static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode(int x) {
            val = x;
        }
    }

}


